import java.util.ArrayList;


public class BinaryTree<T> {
	private TreeNode<T> root;
	
	BinaryTree (TreeNode<T> r){
		root = r;
	}
	BinaryTree(){
		root = null;
	}
	public TreeNode<T> getRoot(){
		return root;
	}
	public BinaryTree<T> setRoot(TreeNode<T> r){
		root = r;
		return this;
	}
	public boolean isEmpty(){
		return root==null;
	}
	
	public String inOrder(){
		return inOrder(root);
	}
	public String postOrder(){
		return postOrder(root);
	}
	public String preOrder(){
		return preOrder(root);
	}
	
	public String levelOrder(){
		String s="";
		ArrayList<String> a = new ArrayList<String>();
		a = levelOrder(root,0,a);
		for (int i=0; i<a.size();i++)
			s += a.get(i);
		return s;
	}

	private ArrayList<String> levelOrder(TreeNode<T> r, int i, ArrayList<String> a){
		String s;
		if (r != null){
			while(i>=a.size())
				a.add("");
			s = a.get(i) + r.toString()+ " ";
			a.remove(i);
			a.add(i, s);
			levelOrder(r.getLeft(),  i+1,a);
			levelOrder(r.getRight(), i+1,a);
			
		}
		return a;
	}
	private String inOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += inOrder(r.getLeft());
			s += r.toString()+" ";
			s += inOrder(r.getRight());
		}
		return s;
	}
	private String postOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += postOrder(r.getLeft());
			s += postOrder(r.getRight());
			s += r.toString()+" ";
		}
		return s;
	}
	private String preOrder (TreeNode<T> r){
		String s= "";
		if(r != null){
			s += r.toString()+" ";
			s += preOrder(r.getLeft());
			s += preOrder(r.getRight());
		}
		return s;
	}
}
